package previous.Test_0121;

/**
 * Created with Intellij IDEA
 * Description:
 * User: 星辰
 */
public class Soution {
    //滑动窗口
    //1.长度最小的子数组
    //暴力枚举
    //单调性，”同向双指针“==”滑动窗口“
    //滑动窗口的使用条件：当暴力枚举时，发现那个可以使用双指针不后退
    //使用方法：
    //1.left=0，right=0；
    //2.进窗口
    //3.判断：出窗口
    //思路：
   /* left=0；right=0；
     1.right向右移动，sum加上right上的元素，
     2.判断sum是否大于target，
     如果大于，退出窗口，left++，将sum减去left的前一个数
     3.如果小于,继续向右移动
     4.随后判断sum是否大于target，
      如果大于left++*/
    public int minSubArrayLen(int target, int[] nums) {
        int n=nums.length;
        int sum=0;
        int len=Integer.MAX_VALUE;
        for (int left = 0, right=0; right <n ; right++) {
            sum+=nums[right];
                /*
                len++;
                if(min>len){
                    min=len;
                }*/
            while( sum>=target){
                len=Math.min(len,right-left+1);
                sum-=nums[left];
                left++;
            }
        }
        return len==Integer.MAX_VALUE?0:len;
    }
    //无重复字符的最长子串
    //1.暴力枚举+哈希表(判断字符是否出现重复)
    //1.right向右移动，将right对应下标的字符放到对应的哈希表中；
    //如果遇到相同的字符，那么r=hash[s[right]]>1;
    //如果大于1，那么表示遇到相同的字符，那么将移动到该重复字符位置之后，并将，该字符在hash中的位置减小为1
    //记录最大长度
    public int lengthOfLongestSubstring(String ss) {
        char[] s=ss.toCharArray();
        int[] hash=new int[128];
        int left=0,right=0,n=ss.length();
        int ret=0;
        while(right<n){
            hash[s[right]]++;
            while(hash[s[right]]>1)
                hash[s[left++]]--;
            ret=Math.max(ret,right-left+1);
            right++;
        }
        return ret;
    }
    public int lengthOfLongestSubstring1(String s) {
        //将字符串转为字符数组
        char[] ss=s.toCharArray();
        //用数组模拟一个哈希表
        int[] hash=new int[128];
        int left=0,right=0,n=s.length(),ret=0;
        while(right<n){
            hash[ss[right]]++;
            while(hash[ss[right]]>1){
                left++;
                hash[ss[left]]--;
            }
            ret=Math.max(ret,right-left+1);
            right++;
        }
        return ret;
    }
    //最大连续1得到个数
    //解法一：暴力枚举+zero计数器；
    //解法二： 滑动窗口
   /* left=0，right=0
    进窗口：
    如果是1无视，0计数
    right向右移动，如果是0，计数，
    判断:出窗口
    直到num>k
    left向右移动，如果遇到0，将0的数减少，直到num<=k
    更新结果
    ret=Math.max(ret,right-left+1);*/
    public int longestOnes1(int[] nums, int k) {
          int left=0;
          int right=0;
          int n=nums.length;
          int count=0;
          int ret=0;
          while(right<n){
              if(nums[right]==0){
                  count++;
              }
              while(count>k){
                  if(nums[left++]==0){
                      count--;
                  }
              }
              right++;
              ret=Math.max(ret,right-left+1);
          }
          return ret;
    }
    public int longestOnes(int[] nums, int k) {
        int ret=0;
        for (int right = 0,left=0,count=0; right <nums.length ; right++) {
            if(nums[right]==0){
                count++;
            }
            while(count>k){
                if(nums[left++]==0){
                    count--;
                }
            }
            ret =Math.max(ret,right-left+1);
        }
        return ret;
    }
    //将x减到0最小操作数
     //解法：滑动窗口
    //策略：正难则反；
    //找最短的操作数；
    //转化：找出最长的子数组，所有元素之和等于sum-x
    //left=0，right=0；
   /* 1.进窗口；
     sum+=nums[right]<targrt
    判断：
    sum>target;
    left++
    出窗口
    更新结果*/
    //思路：
   /* 1.如果要找的数，值很大，也就是target<0,return -1;
    2.判断：将前几个数进行相加，直到大于target
       出窗口：如果大于target，那么就减去前一个数，将left的值进行相加；
    2.进窗口：不大于就继续相右加；
    3.更新结果：如果等于，那么就算出他的长度，寻找最大长度；
    z注意，如果ret=-1，直接返回ret；
    最后将总长度，减去最大长度；*/
    public int minOperations(int[] nums, int x) {
          int left=0,right=0;
          int sum=0,ret=-1;
          int n=nums.length;
        for (int i = 0; i < n; i++) {
            sum+=nums[i];
        }
        int target=sum-x;
        //如果要找的数，值很大
        if(target<0){
            return -1;
        }
        sum=0;
        while(right<n) {
            sum += nums[right];
            while (sum > target) {
                sum -= nums[left];
                left++;
            }
            if (sum == target) {
                ret = Math.max(ret, right - left + 1);
            }
            right++;
        }
        if(ret==-1){
            return -1;
        }
        return n-ret;
    }
}
